import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1734. 解码异或后的排列
 * https://leetcode-cn.com/problems/decode-xored-permutation/
 */
public class Solutions_1734 {
    public static void main(String[] args) {
        List<int[]> inputs = new ArrayList<>();
        int[] nums1 = {3, 1};  // output: {1, 2, 3}
        int[] nums2 = {6, 5, 4, 6};  // output: {2, 4, 1, 5, 3}

        inputs.add(nums1);
        inputs.add(nums2);

        for (int[] input : inputs) {
            int[] result = decode(input);
            System.out.println(Arrays.toString(result));
        }
    }

    /**
     * 与 1732 类似，但是本题因为没有给定基准值，所以难度更大，需要 coder 自己计算出一个基准值出来
     * 根据题目中给定的条件：
     * 共有前 n 个正整数（长度为 encoded.length + 1）
     * 以 encoded = {6, 5, 4, 6} 为例：
     * 可以确定整数数组 prem 的长度为 5，且数组中的元素为：{1, 2, 3, 4, 5}（原数组不一定是这个顺序）
     * 并且可以计算出 prem 的所有元素异或结果为：1 ^ 2 ^ 3 ^ 4 ^ 5 = 1
     * 如何计算出基准值呢？
     * 根据等式
     * 异或结果 1 == a ^ b ^ c ^ d ^ e
     * 异或结果 1 == a ^ 5 ^ 6（已知 b ^ c = 5, d ^ e = 6）
     * a == 1 ^ 5 ^ 6
     * a = 2，即第 1 位的基准值为 2
     */
    public static int[] decode(int[] encoded) {
        int len = encoded.length;
        int xor = 1;
        // 计算出前 len 个正整数的异或值
        for (int i = 2; i <= len + 1; i++) {
            xor = xor ^ i;
        }
        // 根据等式计算出基准值
        int stand = xor;
        for (int i = 1; i < len; i += 2) {
            stand = stand ^ encoded[i];
        }
        // 根据基准值，像 1732 题一般，计算出整个数组的值
        int[] res = new int[len + 1];
        res[0] = stand;
        for (int i = 1; i < res.length; i++) {
            res[i] = res[i - 1] ^ encoded[i - 1];
        }
        return res;
    }
}
